#define _CRT_SECURE_NO_WARNINGS 1

//leetcode114-二叉树的前序遍历
// 二叉树节点个数
int GetBinaryTreeSize(struct TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return GetBinaryTreeSize(root->left) + GetBinaryTreeSize(root->right) + 1;
}

//二叉树的前序遍历
//根 左子树 右子树
void PrevOrder(int* ret, struct TreeNode* root, int* pi)
{
	if (root == NULL)
	{
		return;
	}

	ret[(*pi)++] = root->val;
	PrevOrder(ret, root->left, pi);
	PrevOrder(ret, root->right, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
	*returnSize = GetBinaryTreeSize(root);
	int* ret = malloc(sizeof(int) * (*returnSize));
	int i = 0;
	PrevOrder(ret, root, &i);

	return ret;
}

//leetcode100-相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
	if (p == NULL && q == NULL)
	{
		return true;
	}
	//到这里p、q不同时为空,一个空，一个非空
	if (q == NULL || p == NULL)
	{
		return false;
	}
	//到这里，p、q同时不为空
	if (p->val != q->val)
	{
		return false;
	}
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

//leetcode101—对称二叉树
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
	if (p == NULL && q == NULL)
	{
		return true;
	}
	if (p == NULL || q == NULL)
	{
		return false;
	}
	if (p->val != q->val)
	{
		return false;
	}
	return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root)
{
	//分别从左右子树开始比较
	return _isSymmetric(root->left, root->right);
}


//leetcode572—另一棵树的子树
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
	if (p == NULL && q == NULL)
	{
		return true;
	}
	//到这里p、q不同时为空,一个空，一个非空
	if (q == NULL || p == NULL)
	{
		return false;
	}
	//到这里，p、q同时不为空
	if (p->val != q->val)
	{
		return false;
	}
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
	if (root == NULL)
	{
		return false;
	}
	if (root->val == subRoot->val)
	{
		if (isSameTree(root, subRoot))
		{
			return true;
		}
	}
	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}